home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Containrs / sa / bag_incl < prev    next >
Text File  |  1996-06-01  |  6KB  |  202 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
  3. -- Copyright (C) 1995, International Computer Science Institute
  4. -- $Id: bag_incl.sa,v 1.7 1996/06/01 21:36:15 gomes Exp $
  5. --
  6. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  7. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  8. -- LICENSE contained in the file: Sather/Doc/License of the
  9. -- Sather distribution. The license is also available from ICSI,
  10. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  11. -------------------------------------------------------------------
  12.  
  13. partial class BAG_INCL{E} is
  14.    -- Partial class for read-only sets that implements other functions
  15.    -- in terms of has and elt!
  16.    -- Until we get partial classes, include using:
  17.    -- include BAG_INCL{E} has->, elt!->,unique!->;
  18.  
  19.    include COMPARE{E};
  20.    
  21.    --           --------- CORE FEATURES (must define) ---------
  22.    stub has(e:E): BOOL; 
  23.    -- Return true if the bag has the element "e"
  24.    
  25.    stub elt!: E;
  26.    -- Yield successive elements of the bag
  27.    
  28.    stub unique!: E;
  29.    -- Yield unique elements of the bag (i.e. as if it were a set)
  30.    
  31.    stub count(e: E): INT;
  32.    -- Return the number of times the element "e" occurs in the bag
  33.    
  34.    stub insert(e:E);
  35.    -- Insert "e" into the bag
  36.    
  37.    stub copy: SAME;
  38.    -- Return a copy of the bag
  39.    
  40.    --              ------ Initialization/Duplication -------
  41.    private internal_create: SAME is return #BAG{E} end;
  42.    -- Default create. Called internally 
  43.    
  44.    --              ------ Access/Measurement -------------
  45.    size: INT is 
  46.       i ::= 0; loop discard ::= elt!; i := i + 1; end;
  47.       return i;
  48.    end;
  49.    
  50.    is_empty: BOOL pre ~void(self) is  
  51.       -- Do not do size=0. Finding size may require iteration
  52.       -- through all elements - quite wasteful for just "is_empty"
  53.       loop e ::= elt!; return false; end;
  54.       return true;
  55.    end;
  56.  
  57.    --              ------ Queries/Comparison --------------
  58.    equals(a:$RO_BAG{E}): BOOL
  59.       pre ~void(self) and ~void(a)
  60.    is
  61.       if size /= a.size then return false end;
  62.       loop e::=unique!; if count(e) /= a.count(e) then return false end end;
  63.       return true
  64.    end;
  65.  
  66.    is_subset(a: $RO_BAG{E}): BOOL
  67.    -- Returns true, if 'a' has all elements with higher occurences
  68.    -- as self.
  69.       pre ~void(self) and ~void(a)
  70.    is
  71.       loop e ::= unique!; if count(e) > a.count(e) then return false end end;
  72.       return true
  73.    end;
  74.  
  75.    --              ------ Conversion ----------------------
  76.    as_array: ARRAY{E} is
  77.       res ::= #ARRAY{E}(size);
  78.       loop res.set!(elt!) end;
  79.       return res;
  80.    end;
  81.  
  82.    str: STR is
  83.       -- Prints out a string version of the array of the components 
  84.       -- that are under $STR
  85.       res ::= #FSTR("{");
  86.       loop res := res+",".separate!(elt_str(elt!));  end;
  87.       res := res + "}";
  88.       return(res.str);
  89.    end;
  90.    
  91.    --              ------ Basic Operations ----------------
  92.    union(a: $RO_BAG{E}): SAME
  93.     -- Returns a set containing all elements being contained in
  94.     -- the sets. The properties of the result are the ones from
  95.     -- the first set.
  96.     -- Neither of the sets may be void.
  97.       pre ~void(self) and ~void(a)
  98.    is
  99.       res ::= copy;
  100.       loop res.insert(a.elt!) end;
  101.       return res
  102.    end;
  103.  
  104.  
  105.    intersection(a: $RO_BAG{E}): SAME
  106.     -- Returns a set containing all elements being contained in
  107.     -- both sets. The properties of the result are the ones from
  108.     -- the first set.
  109.     -- Neither of the sets may be void.
  110.       pre ~void(self) and ~void(a)
  111.    is
  112.       res ::= internal_create;
  113.       loop
  114.      e ::= elt!;
  115.      if a.has(e) then res.insert(e) end
  116.       end;
  117.       return res
  118.    end;
  119.  
  120.    difference(a:$RO_BAG{E}): SAME
  121.    -- Returns a set containing all elements being contained in
  122.    -- self but not in a. The properties of the result are the ones
  123.    -- from the first set.
  124.    -- Neither of the sets may be void.
  125.       pre ~void(self) and ~void(a)
  126.    is
  127.       res ::= internal_create;
  128.       loop
  129.      e ::= elt!;
  130.      if ~a.has(e) then res.insert(e) end
  131.       end;
  132.       return res
  133.    end;
  134.  
  135.    is_disjoint(a:$RO_BAG{E}): BOOL
  136.     -- Returns 'true' if all elements of 'self' are not contained
  137.     -- in 'a' and vice versa.
  138.     -- Neither may be void.
  139.     pre ~void(self) and ~void(a)
  140.    is
  141.       loop if has(a.elt!) then return false end end;
  142.       loop if a.has(elt!) then return false end end;
  143.       return true
  144.    end;
  145.  
  146.    count_if(test:ROUT{E}:BOOL):INT is
  147.       -- The number of elements which satisfy `test'.
  148.       -- Self may be void.
  149.       r::=0; 
  150.       loop if test.call(elt!) then r:=r+1 end   end;
  151.       return r 
  152.    end;
  153.  
  154.    index_of(e: E):INT is
  155.       -- Return index of leftmost element of self which  is equal to "e"
  156.       -- or -1 if there is none. 
  157.       i ::= 0;
  158.       loop r ::= elt!; 
  159.      if elt_eq(e,r) then return i end;
  160.      i := i + 1;
  161.       end; 
  162.       return -1;
  163.    end;
  164.  
  165.    some(test:ROUT{E}:BOOL):BOOL is
  166.       -- True if some element of self satisfies `test'. 
  167.       -- Self may be void.
  168.       loop if test.call(elt!) then return true end  end;
  169.       return false 
  170.    end;
  171.  
  172.    every(test:ROUT{E}:BOOL):BOOL is
  173.       -- True if every element of self satisfies `test'.
  174.       -- Self may be void.
  175.       loop if ~test.call(elt!) then return false end  end; 
  176.       return true 
  177.    end;
  178.  
  179.    notany(test:ROUT{E}:BOOL):BOOL is
  180.       -- True if none of the elements of self satisfies `test'.
  181.       -- Self may be void.
  182.       loop if test.call(elt!) then return false end end; 
  183.       return true 
  184.    end;
  185.    
  186.    notevery(test:ROUT{E}:BOOL):BOOL is
  187.       -- True if not every element of self satisfies `test'.
  188.       -- Self may be void.
  189.       loop if ~test.call(elt!) then return true end  end;
  190.       return false 
  191.    end;
  192.  
  193.    -- ------------------- Implementation ------------------
  194.    private elt_str(e: E): STR is
  195.       -- Return a string representing the element "e"
  196.       typecase e 
  197.       when $STR then return e.str  else return "Unprintable Element" end;
  198.    end;
  199.  
  200. end;
  201. --=============================================================================
  202.